/*

Archivo: "list.h"

Implementación de una lista doblemente ligada genérica.

Autor: Diego Luna

Primera versión: 5-6-2012

*/


#ifndef __LIST_H_INCLUDED
#define __LIST_H_INCLUDED


#include <iostream>
#include <cstdlib>

// Solo se compila en modo de pruebas.
#if (CONTAINER_DEBUG == 1)
#include <cmath>
#include <vector>
#include <algorithm>
#endif

#include "globals.h"
#include "bases.h"

// forward declarations.
#if (HASH_TABLE_NEED_ACCESS_TO_LIST == 1)
template <typename T>
class HASH_TABLE_CLASS_NAME;
#endif


/* ========================= Double_Linked_List - Begin ========================== */
template <typename T>
class Double_Linked_List: public Base_Container<T>
{

public:

	// Iterador bidireccional para la lista.
	typedef Base_Iterator<T, DEFAULT_ITERATOR> DL_List_Iterator;

	// ++++++++++++++++++++++++ Constructores\Destructores - Begin +++++++++++++++++++++++++++++

	// Constructor.
	Double_Linked_List();

	// Constructor copia.
	Double_Linked_List(const Double_Linked_List<T>&);

	// Destructor.
	virtual ~Double_Linked_List();

	// ++++++++++++++++++++++++ Constructores\Destructores - End ++++++++++++++++++++++++++++++++


	// ++++++++++++++++++++++++ Operadores - Begin ++++++++++++++++++++++++++++++++++++++++++++++

	// Operador de asignación.
	Double_Linked_List<T>& operator=(const Double_Linked_List&);

	// Operador de asignación (se sobreescribe para la asignación cuando se hace por
	// desreferencia de punteros a la clase base).
	virtual SetImplementation<T>& operator=(const SetImplementation<T>&);

	// ++++++++++++++++++++++++ Operadores - End ++++++++++++++++++++++++++++++++++++++++++++++++

#if (HASH_TABLE_NEED_ACCESS_TO_LIST == 1)
	// La clase que implementa la tabla de hash
	// necesita acceso a los miembros protegidos que
	// devuelven el predecesor, el sucesor y los
	// extremos para poder generar los propios.
	friend class HASH_TABLE_TEMPLATE_NAME;
#endif

protected:

	// ++++++++++++++++++++++++ Métodos protegidos - Begin ++++++++++++++++++++++++++++++++++++++

	// Métodos sobrescritos - Begin -------------------------------------------------------------

	// Devuelve un puntero al nodo con la clave indicada, devuelve NULL en caso de no encontrarse.
	virtual Base_Node<T>* find_node(const T&) const;

	// Agrega un elemento al contenedor devolviendo un puntero al nodo insertado o NULL si no se insertó.
	virtual Base_Node<T>* add_node(const T&, bool);

	// Elimina un elemento del contenedor.
	// Este método es llamado primero, en
	// caso de devolver "false" se llama al
	// que toma un nodo por parámetro.
    virtual bool delete_node_by_key(const T&, bool&);

	// Elimina un nodo del contenedor.
	virtual void delete_node(Base_Node<T>*);

	// Elimina todos los elementos del contenedor.
	virtual void delete_nodes();

	// Devuelve el sucesor de un nodo.
	virtual Base_Node<T>* next(Base_Node<T>*, Iterator_Type) const;

	// Devuelve el predecesor de un nodo.
	virtual Base_Node<T>* previous(Base_Node<T>*, Iterator_Type) const;

	// Devuelve el primer nodo para un tipo de iterador.
	virtual Base_Node<T>* first(Iterator_Type) const;

	// Devuelve el último nodo para un tipo de iterador.
	virtual Base_Node<T>* last(Iterator_Type) const;

	// Métodos sobrescritos - End ---------------------------------------------------------------

	// ++++++++++++++++++++++++ Métodos protegidos - End ++++++++++++++++++++++++++++++++++++++++


private:

	//-------------------------------------------
	// Clase nodo (privada).

	class List_Node: public Base_Node<T>
	{

	public:

		//************************
		// Atributos de List_Node.

		// Puntero al nodo siguiente.
		List_Node* next_;

		// Puntero al nodo anterior.
		List_Node* previous_;

		//************************


		// ++++++++++++++++++++++++ Constructores\Destructores - Begin ++++++++++++++++++++++++
		// Constructor.
		List_Node(const Double_Linked_List<T>&, const T&);

		// Constructor copia.
		List_Node(const List_Node&);

		// Destructor.
		virtual ~List_Node();
		// ++++++++++++++++++++++++ Constructores\Destructores - End ++++++++++++++++++++++++++


		// ++++++++++++++++++++++++ Operadores - Begin ++++++++++++++++++++++++++++++++++++++++

		// Operador de asignación.
		List_Node& operator=(const List_Node&);

		// ++++++++++++++++++++++++ Operadores - End ++++++++++++++++++++++++++++++++++++++++++
	};

	//-------------------------------------------


	//************************
	// Atributos de Double_Linked_List.

	// Puntero al primer nodo.
	List_Node* head_;

	// Puntero al último nodo.
	List_Node* tail_;
	//************************

	// ++++++++++++++++++++++++ Métodos privados - Begin ++++++++++++++++++++++++++++++++++++++++

	// Devuelve el primer nodo de la lista.
	inline List_Node* first_list_node() const;

	// Devuelve el último nodo de la lista.
	inline List_Node* last_list_node() const;

	// Devuelve el nodo siguiente al dado.
	List_Node* succesor_list_node(List_Node*) const;

	// Devuelve el nodo anterior al dado.
	List_Node* predecessor_list_node(List_Node*) const;

	// Inserta un nodo en la lista con la clave dada.
	List_Node* insert_list_node(const T&, bool);

	// Elimina un nodo de la lista.
	void delete_list_node(List_Node*);

	// Encontrar nodo con clave dada, devolviendo el puntero corespondiente.
	List_Node* find_list_node(const T&) const;

	// Elimina todos los nodos.
	void clear_list_nodes();

	// ++++++++++++++++++++++++ Métodos privados - End ++++++++++++++++++++++++++++++++++++++++++

};

/* ========================= Double_Linked_List - End ============================ */



// ++++++++++++++++++++++++ Constructores\Destructores [Double_Linked_List] - Begin +++++++++++++++++++++++++++++

// Constructor.
template <typename T>
Double_Linked_List<T>::Double_Linked_List(): head_(NULL), tail_(NULL)
{
}

// Constructor copia.
template <typename T>
Double_Linked_List<T>::Double_Linked_List(const Double_Linked_List<T>& dll): 
Base_Container<T>(dll), head_(NULL), tail_(NULL)
{
	// LLamo al operador de asignación.
	*this = dll;
}

// Destructor.
template <typename T>
Double_Linked_List<T>::~Double_Linked_List()
{
	// Libero toda la memoria utilizada.
	Base_Container<T>::wipe();
}

// ++++++++++++++++++++++++ Constructores\Destructores [Double_Linked_List] - End ++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Constructores\Destructores [Double_Linked_List<T>::List_Node] - Begin +++++++++++++++++

// Constructor.
template <typename T>
Double_Linked_List<T>::List_Node::List_Node(const Double_Linked_List<T>& container, const T& key):
Base_Node<T>(container, key), next_(NULL), previous_(NULL)
{
}

// Constructor copia.
template <typename T>
Double_Linked_List<T>::List_Node::List_Node(const List_Node& node):
Base_Node<T>(node), next_(NULL), previous_(NULL)
{
	// LLamo al operador de asignación.
	*this = node;
}

// Destructor.
template <typename T>
Double_Linked_List<T>::List_Node::~List_Node()
{
}

// ++++++++++++++++++++++++ Constructores\Destructores [Double_Linked_List<T>::List_Node] - End +++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [Double_Linked_List<T>::List_Node] - Begin +++++++++++++++++++++++++++++++++

// Operador de asignación.
template <typename T>
typename Double_Linked_List<T>::List_Node& Double_Linked_List<T>::List_Node::operator=(const List_Node& ln)
{
	// Verifico la autoasignación.
	if (&ln == this)
		return *this;

	// Llamo al operador de asignación de la clase base.
	Base_Node<T>::operator=(ln);

	// Retorno un referencia al propio nodo.
	return *this;
}

// ++++++++++++++++++++++++ Operadores [Double_Linked_List<T>::List_Node] - End +++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos protegidos [Double_Linked_List] - Begin +++++++++++++++++++++++++++++++++++++++

// Métodos sobrescritos - Begin -------------------------------------------------------------

// Devuelve un puntero al nodo con la clave indicada, devuelve NULL en caso de no encontrarse.
template <typename T>
Base_Node<T>* Double_Linked_List<T>::find_node(const T& key) const
{
	return find_list_node(key);
}

// Agrega un elemento al contenedor devolviendo un puntero al nodo insertado o NULL si no se insertó.
template <typename T>
Base_Node<T>* Double_Linked_List<T>::add_node(const T& key, bool accept_repeated)
{
	return insert_list_node(key, accept_repeated);
}

// Elimina un elemento del contenedor.
// Este método es llamado primero, en
// caso de devolver "false" se llama al
// que toma un nodo por parámetro.
template <typename T>
bool Double_Linked_List<T>::delete_node_by_key(const T&, bool&)
{
	return false;
}

// Elimina un nodo del contenedor.
template <typename T>
void Double_Linked_List<T>::delete_node(Base_Node<T>* n)
{
	Double_Linked_List<T>::List_Node* node = static_cast<Double_Linked_List<T>::List_Node*>(n);

	delete_list_node(node);
}

// Elimina todos los elementos del contenedor.
template <typename T>
void Double_Linked_List<T>::delete_nodes()
{
	// Libero toda la memoria utilizada.
	clear_list_nodes();
}

// Devuelve el sucesor de un nodo.
template <typename T>
Base_Node<T>* Double_Linked_List<T>::next(Base_Node<T>* n, Iterator_Type) const
{
	Double_Linked_List<T>::List_Node* node = static_cast<Double_Linked_List<T>::List_Node*>(n);

	return succesor_list_node(node);
}

// Devuelve el predecesor de un nodo.
template <typename T>
Base_Node<T>* Double_Linked_List<T>::previous(Base_Node<T>* n, Iterator_Type) const
{
	Double_Linked_List<T>::List_Node* node = static_cast<Double_Linked_List<T>::List_Node*>(n);

	return predecessor_list_node(node);
}

// Devuelve el primer nodo para un tipo de iterador.
template <typename T>
Base_Node<T>* Double_Linked_List<T>::first(Iterator_Type) const
{
	return first_list_node();
}

// Devuelve el último nodo para un tipo de iterador.
template <typename T>
Base_Node<T>* Double_Linked_List<T>::last(Iterator_Type) const
{
	return last_list_node();
}

// Métodos sobrescritos - End ---------------------------------------------------------------

// ++++++++++++++++++++++++ Métodos protegidos  [Double_Linked_List] - End +++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos privados [Double_Linked_List] - Begin ++++++++++++++++++++++++++++++++++++++++

// Devuelve el primer nodo de la lista.
template <typename T>
typename Double_Linked_List<T>::List_Node* Double_Linked_List<T>::first_list_node() const
{
	return head_;
}

// Devuelve el último nodo de la lista.
template <typename T>
typename Double_Linked_List<T>::List_Node* Double_Linked_List<T>::last_list_node() const
{
	return tail_;
}

// Devuelve el nodo siguiente al dado.
template <typename T>
typename Double_Linked_List<T>::List_Node* Double_Linked_List<T>::succesor_list_node(List_Node* node) const
{
	if (node == NULL)
		return NULL;
	else
		return node->next_;
}

// Devuelve el nodo anterior al dado.
template <typename T>
typename Double_Linked_List<T>::List_Node* Double_Linked_List<T>::predecessor_list_node(List_Node* node) const
{
	if (node == NULL)
		return NULL;
	else
		return node->previous_;
}

// Inserta un nodo en la lista con la clave dada.
template <typename T>
typename Double_Linked_List<T>::List_Node* Double_Linked_List<T>::insert_list_node(const T& key, bool accept_repeated)
{
	if (!accept_repeated && (find_list_node(key) != NULL))
		return NULL;

	// Creo un nuevo nodo.
	List_Node* node = new List_Node(*this, key);

	if (tail_ == NULL)
	{
		tail_ = node;
		head_ = node;
	}
	else
	{
		node->previous_ = tail_;

		tail_->next_ = node;

		tail_ = node;
	}

	return node;
}

// Encontrar nodo con clave dada, devolviendo el puntero corespondiente.
template <typename T>
typename Double_Linked_List<T>::List_Node* Double_Linked_List<T>::find_list_node(const T& key) const
{
	if (head_ == NULL)
		return NULL;
	else
	{
		List_Node* curr = head_;

		while (curr != NULL)
		{
			if (curr->key_ == key)
				return curr;
			else
				curr = curr->next_;
		}

		return NULL;
	}
}

// Elimina un nodo de la lista.
template <typename T>
void Double_Linked_List<T>::delete_list_node(List_Node* node)
{
	// Si no apunta  a un nodo no hago nada.
	if (node == NULL)
		return;

	// Si el nodo tiene previo o es el primero.
	if (node->previous_ != NULL)
		node->previous_->next_ = node->next_;
	else
		head_ = node->next_;

	// Si el nodo tiene siguiente o es el último.
	if (node->next_ != NULL)
		node->next_->previous_ = node->previous_;
	else
		tail_ = node->previous_;

	delete node;
}

// Elimina todos los nodos.
template <typename T>
void Double_Linked_List<T>::clear_list_nodes()
{
	List_Node* curr;

	while (head_ != NULL)
	{
		head_ = (curr = head_)->next_;
		delete curr;
	}

	tail_ = NULL;
}

// ++++++++++++++++++++++++ Métodos privados [Double_Linked_List] - End ++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [Double_Linked_List] - Begin ++++++++++++++++++++++++++++++++++++++++++++++

// Operador de asignación.
template <typename T>
Double_Linked_List<T>& Double_Linked_List<T>::operator=(const Double_Linked_List& dll)
{
	// Verifico la autoasignación.
	if (&dll == this)
		return *this;

	// Llamo al operador de asignación de la clase base.
	Base_Container<T>::operator=(dll);

	// Puntero al nodo actual a copiar.
	List_Node* curr_org = dll.head_;

	// Puntero a la copia actual.
	List_Node* curr = NULL;

	// Puntero a la copia previa.
	List_Node* prev = NULL;

	while (curr_org != NULL)
	{
		// Copio el nodo actual.
		curr = new List_Node(*curr_org);

		// Asigno la "cabeza" de la lista si es el nodo copiado.
		if (curr_org == dll.head_)
			head_ = curr;

		// Asigno el puntero al anterior del actual.
		curr->previous_ = prev;

		// Asigno el puntero al siguiente del anterior.
		if (prev != NULL)
			prev->next_ = curr;

		// Actualizo el puntero al previo.
		prev = curr;

		// avanzo al siguiente nodo a copiar.
		curr_org = curr_org->next_;
	}

	// Asigno el terminador NULL de la "cola" de la lista.
	if (curr != NULL)
		curr->next_ = NULL;

	// Asigno la "cola" de la lista.
	tail_ = curr;

	return *this;
}

// Operador de asignación (se sobreescribe para la asignación cuando se hace por
// desreferencia de punteros a la clase base).
template <typename T>
SetImplementation<T>& Double_Linked_List<T>::operator=(const SetImplementation<T>& setimpl)
{
	if (typeid(setimpl) != typeid(*this))
		return SetImplementation<T>::operator=(setimpl);
	else
		return operator=(static_cast<const Double_Linked_List<T>& >(setimpl));
}

// ++++++++++++++++++++++++ Operadores [Double_Linked_List] - End ++++++++++++++++++++++++++++++++++++++++++++++++

#endif
